This invention relates to a merge (merging) device used in various systems such as a system for sorting a large amount of data.
Some data sorting systems include a merge device. The merge device has comparators. As will be explained later, in the prior-art merge device, the activity rate or the actually-used rate of the comparators tends to be low.
Before the detailed description of the invention, a prior-art merge device will be explained for a better understanding of this invention.
FIG. 6 shows a prior-art merge device which includes a set of input FIFO (First-In First-Out) buffers 47, 48, 49, 50, 51, 52, 53, and 54, a set of first comparators 62, 63, 64, and 65, a set of first intermediate FIFO buffers 55, 56, 57, and 58. The intermediate FIFO buffers 55-58 have a capacity of two data words and are of the two-stage type. The prior-art merge device also includes a set of second comparators 66 and 67, a set of second intermediate FIFO buffers 59 and 60, a third comparator 68, and an output FIFO buffer 61. The intermediate FIFO buffers 59 and 60 have a capacity of two data words and are of the two-stage type.
The operation of the prior-art merge device of FIG. 6 will be described with reference to FIG. 7. In each of the left-hand head sections for the intermediate FIFO buffers of FIG. 7, the numerals "0" and "1" denote the first word storage part and the second word storage part respectively. In the body sections for the intermediate FIFO buffers of FIG. 7, the natural numbers denote the contents of stored data in a decimal expression while the character "-" denotes that the related buffer is completely empty. In the sections for the comparators of FIG. 7, the character "ON" denotes that the related comparator is operating the character "-" denotes that the related comparator is at rest.
The prior-art merge device of FIG. 6 operates as follows. The comparator 62 compares data at a bottom of the input FIFO buffer 47 and data at a bottom of the input FIFO buffer 48 and reads out a smaller of the two data from one of the FIFO buffers 47 and 48. The comparator 62 transfers the readout data to the intermediate FIFO buffer 55. Similarly, a smaller of two data is transferred from one of the input FIFO buffers 49 and 50 to the intermediate FIFO buffer 56 via the comparator 63. A smaller of two data is transferred from one of the input FIFO buffers 51 and 52 to the intermediate FIFO buffer 57 via the comparator 64. A smaller of two-data is transferred from one of the input FIFO buffers 53 and 54 to the intermediate FIFO buffer 58 via the comparator 65. These data comparing and data transferring processes are executed during a period denoted by "TIME 1" in FIG. 7. Thereafter, data are transferred to the intermediate FIFO buffers 55-58 in a similar manner when they become into not-full states. The not-full state means that at least one of the two stages of the related internal FIFO buffer is unoccupied by data.
During a period "TIME 2" in FIG. 7 and later periods, when the intermediate FIFO buffer 59 is in a not-full state, the comparator 66 reads out a smaller of two data from one of the intermediate FIFO buffers 55 and 56 and transfers the readout data to the intermediate FIFO buffer 59. Similarly, when the intermediate FIFO buffer 60 is in a not-full state, the comparator 67 reads out a smaller of two data from one of the intermediate FIFO buffers 57 and 58 and transfers the readout data to the intermediate FIFO buffer 60.
During a period "TIME 3" in FIG. 7 and later periods, the comparator 68 reads out a smaller of two data from one of the intermediate FIFO buffers 59 and 60 and transfers the readout data to the output FIFO buffer 61. Accordingly, during the period "TIME 3" and the later periods, the sorted data are sequentially outputted to the output FIFO buffer 61.
In the prior-art merge device of FIG. 6, as shown in FIG. 7, during a period "TIME 5" and later periods, only three of the seven comparators are operating while the others are at rest. Accordingly, the activity rate of the comparators is low.